type TMatrixItem<L> = [number, ...number[]] & { length: L };
type TMatrix<L> = [TMatrixItem<L>, ...TMatrixItem<L>[]] & { length: L }
export type TSudokuMatrix = TMatrix<9>;

const UNASSIGNED = 0;

function usedInRow(matrix: TSudokuMatrix, row: number, num: number) {
  for (let col = 0; col < matrix.length; col++) {
    if (matrix[row][col] === num) {
      return true;
    }
  }

  return false;
}

function usedInCol(matrix: TSudokuMatrix, col: number, num: number) {
  for (let row = 0; row < matrix.length; row++) {
    if (matrix[row][col] === num) {
      return true;
    }
  }

  return false;
}

function usedInBox(matrix: TSudokuMatrix, boxStartRow: number, boxStartCol: number, num: number) {
  for (let row = 0; row < 3; row++) {
    for (let col = 0; col < 3; col++) {
      if (matrix[boxStartRow + row][boxStartCol + col] === num) {
        return true;
      }
    }
  }

  return false;
}

function isSafe(matrix: TSudokuMatrix, row: number, col: number, num: number) {
  return (
    !usedInRow(matrix, row, num)
    && !usedInCol(matrix, col, num)
    && !usedInBox(matrix, row - (row % 3), col - (col % 3), num)
  );
}

function solveSudoku(matrix: TSudokuMatrix) {
  let row = 0;
  let col = 0;
  let checkBlankSpace = false;

  for (row = 0; row < matrix.length; row++) {
    for (col = 0; col < matrix[row].length; col++) {
      if (matrix[row][col] === UNASSIGNED) {
        checkBlankSpace = true;
        break;
      }
    }
    if (checkBlankSpace === true) {
      break;
    }
  }

  if (checkBlankSpace === false) {
    return true;
  }

  for (let num = 1; num <= 9; num++) {
    if (isSafe(matrix, row, col, num)) {
      matrix[row][col] = num;
      if (solveSudoku(matrix)) {
        return true;
      }
      matrix[row][col] = UNASSIGNED;
    }
  }

  return false;
}

export function sudokuSolver(matrix: TSudokuMatrix) {
  if (solveSudoku(matrix) === true) {
    return matrix;
  }

  return '问题无解';
}
